/**
*
*@author
*@version 1.0
*@className Solution
*@since 1.0
*/

import java.util.*;

/**
 * 力扣解题方法
 */
public class Solution {
    public static void main(String[] args) {

        String multiply = multiply("123456789", "987654321");
        System.out.println(multiply);
//        System.out.println(perfectMove("AAAA"));
//        System.out.println("01234".substring(0, 5));
    }
    public static int perfectMove(String dir) {
//        dir=dir.toLowerCase();
//        //存在map中，key是方向，value是数量
//        //只需要在动态窗口中，找到多出来的那一个方向，修改为缺失的那个方向。
//        //维护窗口时，需要动态更新除窗口外的其他方向的数量。
//        Map<String, Integer> map = new HashMap<>();
//        map.put("w", 0);
//        map.put("a", 0);
//        map.put("s", 0);
//        map.put("d", 0);
//        for (int i = 0; i < dir.length(); i++) {
//            //获取窗口中各个方向的数量，以及缺失和多出的方向
//            map.put(dir.charAt(i) + "", map.get(dir.charAt(i) + "") + 1);
//        }
//        Integer cot = dir.length()/4;
//        if(map.get("w")==cot && map.get("a")==cot && map.get("s")==cot && map.get("d")==cot){
//            return 0;
//        }
//        //维护窗口长度从1开始
//        for (int i = 0; i <= dir.length()-1; i++) {
//            for(int m=0,n=1+i;n<dir.length();m++,n++){
//                //该窗口中所有方向都可以变为任意的方向
//                for (int j = m; j < n; j++) {
//                    map.replace(dir.charAt(j) + "", map.get(dir.charAt(j) + "") - 1);
//                }
//                if(map.get("w")>cot || map.get("a")>cot || map.get("s")>cot || map.get("d")>cot){
//                    //如果非窗口中还有多余的方向，就需要换窗口
//                    for (int j = m; j < n; j++) {
//                        map.replace(dir.charAt(j) + "", map.get(dir.charAt(j) + "") + 1);
//                    }
//                    continue;
//                }else{
//                    return n-m;
//                }
//            }
//        }
//        return 0;
        dir = dir.toLowerCase();
        Map<String, Integer> map = new HashMap<>();
        map.put("w", 0);
        map.put("a", 0);
        map.put("s", 0);
        map.put("d", 0);

        // 统计所有方向的数量
        for (int i = 0; i < dir.length(); i++) {
            map.put(dir.charAt(i) + "", map.get(dir.charAt(i) + "") + 1);
        }

        int cot = dir.length() / 4;
        if (map.get("w") == cot && map.get("a") == cot && map.get("s") == cot && map.get("d") == cot) {
            return 0;
        }

        Map<String, Integer> windowMap = new HashMap<>();
        windowMap.put("w", 0);
        windowMap.put("a", 0);
        windowMap.put("s", 0);
        windowMap.put("d", 0);

        int left = 0, right = 0;
        int minWindowLength = dir.length();

        while (right < dir.length()) {
            // 将right位置的字符加入窗口
            windowMap.put(dir.charAt(right) + "", windowMap.get(dir.charAt(right) + "") + 1);
            right++;

            // 检查窗口是否满足条件
            while (isValid(windowMap, map, cot)) {
                // 更新最小窗口长度
                minWindowLength = Math.min(minWindowLength, right - left);
                // 将left位置的字符移出窗口
                windowMap.put(dir.charAt(left) + "", windowMap.get(dir.charAt(left) + "") - 1);
                left++;
            }
        }

// 返回结果
        return minWindowLength == dir.length() ? 0 : minWindowLength;
    }
    // 辅助函数：判断当前窗口内的方向数量是否可以使得整个字符串满足条件
    private static boolean isValid(Map<String, Integer> windowMap, Map<String, Integer> map, int cot) {
        return map.get("w") - windowMap.get("w") <= cot &&
                map.get("a") - windowMap.get("a") <= cot &&
                map.get("s") - windowMap.get("s") <= cot &&
                map.get("d") - windowMap.get("d") <= cot;
    }

    private static String fzdir(String dir) {
        int x = 0;
        int y = 0;
        for (int i = 0; i < dir.length(); i++) {
            if (dir.charAt(i) == 'w') {
                y--;
            } else if (dir.charAt(i) == 'a') {
                x++;
            } else if (dir.charAt(i) =='s') {
                y++;
            } else if (dir.charAt(i) == 'd') {
                x--;
            }
        }
        return x + "," + y;
    }

    //根据方向计算出在x和y轴的位移距离“x+，+y”
    private static String move(String dir) {
        int x = 0;
        int y = 0;
        for (int i = 0; i < dir.length(); i++) {
            if (dir.charAt(i) == 'w') {
                y++;
            } else if (dir.charAt(i) == 'a') {
                x--;
            } else if (dir.charAt(i) =='s') {
                y--;
            } else if (dir.charAt(i) == 'd') {
                x++;
            }
        }
        return x + "," + y;
    }
    //存两个map，分别是左右对立，位移一段就将存于queue中，判断在x和y轴上的位移是否为0
    private static Boolean isBack(String dir) {
        //维护两个int，x和y。
        String move = move(dir);
        int x = Integer.parseInt(move.split(",")[0]);
        int y = Integer.parseInt(move.split(",")[1]);
        //判断是否回到原点
        if (x == 0 && y == 0) {
            return true;
        }
        return false;
    }

    /**
     * 字符串相乘
     * 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
     * 示例 1:
     * 输入: num1 = "2", num2 = "3"
     * 输出: "6"
     * 示例 2:
     * 输入: num1 = "123", num2 = "456"
     * 输出: "56088"
     * 说明：
     * num1 和 num2 的长度小于110。
     * num1 和 num2 只包含数字 0-9。
     * num1 和 num2 均不以零开头，除非是数字 0 本身。
     * 不能使用任何标准库的大数类型（比如 BigInteger）。
     * @param num1
     * @param num2
     * @return
     */
    public static String multiply(String num1, String num2) {

        //1、遍历两个数，分别从最后一位开始乘，模拟乘法运算

        //将数位小的作为num2
        if(num1.length()<num2.length()){
            String temp = num1;
            num1 = num2;
            num2 = temp;
        }
        String result = "";
        String end = "",end2 = "";
        for (int i = num2.length() - 1; i >= 0; i--)
        {
            int temp = 0;
            for (int j = num1.length() - 1; j >= 0; j--){
                //计算当前位的乘积
                int curX = (num2.charAt(i) - '0') * (num1.charAt(j) - '0');
                curX += temp;
                //更新进位
                temp = curX / 10;
                //更新当前位的值
                curX = curX % 10;
                //将当前位的值添加到结果中，结果是字符串，添加到最后一位的前一位
                result = curX + result;
            }
            if (temp > 0){
                result = temp + result;
            }
            //末尾0的数量
            for(int k=i;k<num2.length()-1;k++){
                result = result + "0";
            }
            for(int k=0;k<result.length();k++){
                if(end.length()<result.length()){
                    end =  "0"+end;
                }
            }
            //初始化end
            int temp2 = 0;
            for (int j=result.length()-1;j>=0;j--){
                int curX = (end.charAt(j) - '0') + (result.charAt(j) - '0')+temp2;
                temp2 = curX / 10;
                curX = curX % 10;
                end2 = curX + end2;
            }
            end = end2;
            end2 = "";
            result = "";
        }
        int k=0;
        for(;k<end.length();k++){
            if(end.charAt(k)!='0'){
                break;
            }
        }
        if(k==end.length()){
            return "0";
        }
        return end;
    }
    /**
     * 组合总和 II
     * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
     * candidates 中的每个数字在每个组合中只能使用一次。
     * 说明：
     * 所有数字（包括目标数）都是正整数。
     * 解集不能包含重复的组合。
     * 示例 1:
     * 输入: candidates = [10,1,2,7,6,1,5], target = 8
     * 输出:
     * [
     *   [1,7],
     *   [1,2,5],
     *   [2,6],
     *   [1,1,6]
     * ]
     * 示例 2:
     * 输入: candidates = [2,5,2,1,2], target = 5
     * 输出:
     * [
     *   [1,2,2],
     *   [5]
     * ]
     * @param candidates
     * @param target
     * @return
     */
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {

        return null;
    }
}
